package com.lry.basic.algorithm.common;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/10/10
 */

import java.util.Stack;

/**
 * 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 * 示例:
 * board =
 * [
 *   ['A','B','C','E'],
 *   ['S','F','C','S'],
 *   ['A','D','E','E']
 * ]
 *
 * 给定 word = "ABCCED", 返回 true.
 * 给定 word = "SEE", 返回 true.
 * 给定 word = "ABCB", 返回 false.
 *
 */
public class WordSearch1 {
    public static void main(String[] args) {
        System.out.println(
                new WordSearch1().exist(
                new char[][]{{'A','C','C','F'},{'S','F','C','S'},{'A','D','E','E'}},
                "FCSEEDAS"));
    }
    private int m,n;
    private int[][] direction = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
    private boolean[][] mark;

    public boolean exist(char[][] board, String word) {
        m = board.length;
        if(m==0||word.length()==0)return false;
        n = board[0].length;
        mark = new boolean[m][n];

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(dfs(board,word,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int i, int j,int index) {
        if(word.charAt(index)==board[i][j]){
            if(index==word.length()-1){
                return word.charAt(index)==board[i][j];
            }
            mark[i][j] = true;
            for(int k=0;k<4;k++){
                int newI = i+direction[k][0];
                int newJ = j+direction[k][1];
                //在范围内，相等，没有被占
                if(inRange(newI,newJ)&&word.charAt(index+1)==board[newI][newJ]&&!mark[newI][newJ]){
                    if(dfs(board,word,newI,newJ,index+1)){
                        return true;
                    }
                }
            }
            mark[i][j] = false;
        }
        return false;
    }


    private boolean inRange(int i,int j){
        if(i>=0&&i<m&&j>=0&&j<n){
            return true;
        }
        return false;
    }
}
